public class AVLTree {
    public TreeNode root;

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);

        //如果根节点本身为空就直接赋值
        if(root == null) {
            root = node;
            return true;
        }

        TreeNode prev = null;
        TreeNode cur = root;

        //找到新结点的位置
        while(cur != null) {
            if(cur.val == val) {
                //相同的数据无法再次插入
                return false;
            } else if(cur.val < val) {
                prev = cur;
                cur = cur.right;
            } else {
                prev = cur;
                cur = cur.left;
            }
        }

        //插入结点
        if(prev.val > val) {
            prev.left = node;
        } else {
            prev.right = node;
        }
        node.parent = prev;

        cur = node;

        //调整平衡因子与AVL树
        while(prev != null) {
            //左子树-- 右子树++
            if(prev.left == cur) {
                prev.bf--;
            } else {
                prev.bf++;
            }

            //检查是否需要旋转
            if(prev.bf == 0) {
                //平衡因子为0，说明树已经平衡，不用调整
                break;
            } else if(prev.bf == -1 || prev.bf == 1) {
                //如果出现 -1 或者 1 则说明树的平衡性已经被新结点影响到，需要继续调整
                cur = prev;
                prev = prev.parent;
            } else {
                //此时怕平衡因子有两种情况2 或者 -2，需要旋转重新建立平衡树
                if(prev.bf == 2) {
                    //说明右子树过高
                    if(cur.bf == 1) {
                        //右右型 左单旋
                        rotateLeft(prev);
                    } else if(cur.bf == -1) {
                        //右左型 右左双旋
                        rotateRL(prev);
                    }

                } else {
                    //此时 prev.bf == -2 说明左子树过高
                    if(cur.bf == 1) {
                        //左右型，左右双旋
                        rotateLR(prev);
                    } else if(cur.bf == -1) {
                        //左左型， 右单旋
                        rotateRight(prev);
                    }

                }

                //旋转完成后，树已经平衡，直接退出循环
                break;
            }
        }

        return true;
    }

    //左右双旋
    private void rotateLR(TreeNode prev) {
        TreeNode cur = prev.left;
        TreeNode curR = cur.right;
        int bf = curR.bf;

        rotateLeft(cur);
        rotateRight(prev);

        //调整平衡因子
        if(bf == 1) {
            cur.bf = -1;
        } else if(bf == -1) {
            prev.bf = 1;
        }

        //bf 为 0 的时候，不需要调整
    }

    //右左双旋
    private void rotateRL(TreeNode prev) {
        TreeNode cur = prev.right;
        TreeNode curL = cur.left;
        int bf = curL.bf;

        rotateRight(cur);
        rotateLeft(prev);

        //调整平衡因子
        if(bf == 1) {
            prev.bf = -1;
        } else if(bf == -1) {
            cur.bf = 1;
        }

        //bf 为 0 的时候，不需要调整
    }

    //右单旋
    private void rotateRight(TreeNode prev) {
        TreeNode pParent = prev.parent;
        TreeNode cur = prev.left;
        TreeNode curR = cur.right;

        prev.left = curR;
        if(curR != null) {
            curR.parent = prev;
        }
        cur.right = prev;
        prev.parent = cur;
        cur.parent = pParent;
        if(prev == root) {
            root = cur;
        } else if(pParent.left == prev) {
            pParent.left = cur;
        } else {
            pParent.right = cur;
        }

        //调整平衡因子
        cur.bf = prev.bf = 0;
    }

    //左单旋
    private void rotateLeft(TreeNode prev) {
        TreeNode pParent = prev.parent;
        TreeNode cur = prev.right;
        TreeNode curL = cur.left;

        prev.right = curL;
        if(curL != null) {
            curL.parent = prev;
        }
        cur.left = prev;
        prev.parent = cur;
        cur.parent = pParent;

        if(prev == root) {
            root = cur;
        } else if(pParent.left == prev) {
            pParent.left = cur;
        } else {
            pParent.right = cur;
        }

        //调整平衡因子
        cur.bf = prev.bf = 0;
    }
}
